<html>
<head>
<title>Project 2 </title>
</head>
<body bgcolor="#ffffff">
<h1 align="center">Project 2 </h1>
<p>
<b>Due Date</b>:  Mar 8, by midnight.
</p>
<p>
[<b>Important Note</b>: If you are reading the <a href="./prj2.umt">./prj2.umt</a> version of this
document, please be aware of the fact that it is really the source code for
the <tt>HTML</tt> <a href="./prj2.html">./prj2.html</a> and <tt>PDF</tt> <a href="./prj2.pdf">./prj2.pdf</a> versions.  Hence it
contains markup; usually the markup is quite unobstrusive, but sometimes it
gets in the way.  In particular, some <tt>*</tt>'s and quotes may not make sense as
they are also used for markup.]
</p>
<p>
The document first describes the aims of this project.  It then gives the
requirements as explicitly as possible.  It describes the files which are
being provided and hints at how the project may be implemented.  Finally, it
lists exactly what needs to be submitted.
</p>
<h2>Aims</h2>
<p>
The aims of this project are as follows:
</p>
<ul>
<p><li>
To allow you to build and structure a reasonably complex program.
</p>
<p><li>
To introduce you to creating and waiting for multiple Unix processes.
</p>
<p><li>
To familiarize you with using anonymous pipes for inter-process
    communication.
</p>
</ul>
<h2>Requirements</h2>
<p>
Write a program which integrates functions using the trapezoidal rule
utilizing a tree of processes.  Specifically, write a program with
executable <tt>prj2</tt> which is invoked as follows:
</p>
<pre>
    $ ./prj2 [-d] N1 N2 ...
</pre>
<p>
where:
</p>
<dl>
<p><dt><tt>-d</tt><dd>
      If specified, then the program will run in a debugging mode
      with debugging messages (specified below) output on standard error.
</p>
<p>
   <tt>N1</tt>, <tt>N2</tt>, ...
      are positive integers (typically small).  At least one
      must be specified.
</p>
</dl>
<p>
If the command-line arguments are not valid, then the program should exit
with a suitable informative error message output to standard error.  Once
the program has validated its command-line arguments, it must start a tree
of processes structured as follows:
</p>
<ul>
<p><li>
The root of the process tree is the initial process.
</p>
<p><li>
The root process should start <tt>N1</tt> child processes.
</p>
<p><li>
Each of the <tt>N1</tt> children of the root process should start
    <tt>N2</tt> child processes.
</p>
<p><li>
The program should continue creating as many levels in the process tree
    as there are command-line arguments (where the root process is regarded
    as being at level 0).  The number of children created at each level is
    specified by the corresponding command-line argument.
</p>
</ul>
<p>
If the debug option <tt>-d</tt> was specified, then each process in the process
tree should print on standard error a line of the form:
</p>
<pre>
  LEVEL:PID
</pre>
<p>
where <tt>LEVEL</tt> is the level of the process in the process tree and <tt>PID</tt>
is its process id.
</p>
<p>
Once the process tree has been setup, the program should enter a I/O loop
with behavior identical to that of <a href="../prj1/prj1.html">prj1</a>.
Specifically, when run, the program should read lines from standard input,
with each line containing 4 whitespace separated tokens:
</p>
<pre>
    FN LO_BOUND HI_BOUND N_INTERVALS
</pre>
<p>
where:
</p>
<dl>
<p><dt><tt>FN</tt><dd>
    is the name of a function known by the program referring to the
    function which is to be integrated.
</p>
<p><dt><tt>LO_BOUND</tt><dd>
    is the textual representation of a <tt>double</tt> representing the
    lower bound of a integral.
</p>
<p><dt><tt>HI_BOUND</tt><dd>
    is the textual representation of a <tt>double</tt> representing the
    upper bound of a integral.
</p>
<p><dt><tt>N_POINTS</tt><dd>
    is the textual representation of a <tt>int</tt> representing the
    number of points over which the integral should be evaluated.
</p>
</dl>
<p>
The program should then print on standard output a line containing the
result of evaluating the integral of <tt>FN</tt> from <tt>LO_BOUND</tt> to <tt>HI_BOUND</tt>
using the <a href="http://en.wikipedia.org/wiki/Trapezoidal_rule">trapezoidal-rule</a>
using <tt>N_POINTS</tt> points.  The result should be printed using the <tt>printf</tt>
format <tt>%.6g</tt>.
</p>
<p>
Additionally, if the debug option <tt>-d</tt> has been specified when invoking the
program then each process should output onto standard error a line with the
following format:
</p>
<pre>
    LEVEL:PID FN LO_BOUND HI_BOUND N_POINTS
</pre>
<p>
where <tt>LEVEL</tt> and <tt>PID</tt> are as before, <tt>FN</tt> is the name of the function
being integrated, <tt>LO_BOUND</tt> and <tt>HI_BOUND</tt> are the bounds for that process
output using format <tt>%g</tt> and <tt>N_POINTS</tt> are the number of points for that
process.
</p>
<p>
The work of the integration is to be divided within the process tree as
follows:
</p>
<ul>
<p><li>
The integration range and number of intervals will be divided
    approximately evenly over the process tree.
</p>
<p><li>
Only processes which are leaves of the process tree will do integration.
</p>
<p><li>
Processes which are non-leaves in the process tree will merely sum up
    the results computed by their children and return the sum up the process
    tree.
</p>
<p><li>
The root process will output its result sum to standard output as per
    the program specifications.
</p>
</ul>
<p>
For example, if we have a process tree specified by command-line arguments
<tt>3 2</tt>, then we will have a total of 10 processes:
</p>
<ol type="0">
<p><li>
A single root process at level 0. When the program started up, this
     process would have created 3 children at level 1.  It will read and
     parse the program input from standard input: assume that it has to
     integrate a function over the range [-3, +3] using 1001 points. It will
     convey this work to its children, broken up roughly equally over its 3
     children (see below).  As each child returns a result, it will merely
     sum the results computed by its children and output the sum to
     standard output.
</p>
<p><li>
There will be 3 processes at level 1 with responsibilities roughly
     divided up as follows (for the example given above):
<ol type="a">
<p><li>
333 points over the bounds [-3 + 0<tt>*</tt>6/1000, -3 + 332<tt>*</tt>6/1000]
</p>
<p><li>
333 points over the bounds [-3 + 333<tt>*</tt>6/1000, -3 + 665<tt>*</tt>6/1000].
</p>
<p><li>
335 points over the bounds [-3 + 666<tt>*</tt>6/1000, -3 + 1000<tt>*</tt>6/1000].
</p>
</ol>
<p>
     Each of these processes should create 2 children.  Each level 1 process
     will merely compute the sum of the results computed by its children and
     return that result to the root process.
</p>
</p>
<p><li>
There will be 6 processes at level 2: 2 children created by each of the
     3 processes in level 1. Each level 1 process will divide its
     responsibilities roughly equally over its children.  For the example
     above, the level 1 process responsible for 333 steps over [-3 +
     0<tt>*</tt>6/1000, -3 + 332<tt>*</tt>6/1000] will create two level 2 processes with
     responsibilities roughly as follows:
<ol type="a">
<p><li>
166 steps over [-3 + 0<tt>*</tt>6/1000, -3 + 165<tt>*</tt>6/1000].
</p>
<p><li>
167 steps over [-3 + 166<tt>*</tt>6/1000, -3 + 332<tt>*</tt>6/1000].
</p>
</ol>
<p>
     Each of the level 2 processes should perform the integration
     over the specified range and number of steps using the trapezoidal
     integration algorithm.
</p>
</p>
</ol>
<p>
The functions being integrated should be provided to the program using a
object module <tt>fns.o</tt> compiled from a C module <tt>fns.c</tt> which provides
an ADT via the following two functions:
</p>
<pre>
typedef double (*FnP)(double);

/** Return function pointer for name. Returns NULL on failure. */
FnP getFunctionByNameString(const char *name);


/** Return function pointer for function with name having nChars
 *  characters. Returns NULL on failure.
 */
FnP getFunctionByCharArray(char[] name, int nChars);
</pre>
<p>
The implementation is subject to the following additional restrictions:
</p>
<ul>
<p><li>
All IPC must be performed using only half-duplex anonymous pipes.
</p>
<p><li>
The program should check for input errors and if it encounters an error
    it should output a meaningful error message to standard error and then
    continue evaluating the next line.
</p>
<p><li>
The program should check for all resource errors and terminate after
    outputting a meaningful error message to standard error.
</p>
<p><li>
All processes should be cleaned up on normal program termination due to
    EOF (this is not required if the program terminates for an abnormal
    reason like a resource allocation error).
</p>
<p><li>
There should not be any implementation limits beyond those caused by
    resource limitations.  For example, there should not be any fixed
    limit on the length of the name of the function being integrated,
    the number of processes supported or the number of levels in the
    process tree.
</p>
</ul>
<h2>Provided Files</h2>
<p>
The <tt>cs551</tt> <a href="../../include/">library</a> provided for the previous project has
not been changed and can also be used for this project.  Additionally, the
following files have been provided in the <a href="./files/">./files/</a> directory:
</p>
<dl>
<p><dt><a href="./files/Makefile">Makefile</a><dd>
    This file can be used to build your overall project by simply invoking
    the command <tt>make</tt> in the directory containing it and all source files.
    It assumes that your code is setup in the following files:
</p>
<ul>
<p><li>
<tt>fns.h</tt> with implementation file <tt>fns.c</tt> defining the functions
        available for integration.
</p>
<p><li>
<tt>trapezoidal.h</tt> with implementation file <tt>trapezoidal.c</tt> defining
        the code which implements the integration of a function (specified
        by a function pointer) from some lower bound to some upper bound
        (specified by <tt>double</tt>'s) using the trapezoidal rule over some
        number of points (specified by an <tt>int</tt>).
</p>
<p><li>
<tt>main.c</tt> which contains the main program and code which repeatedly
        reads and parses input lines, sets up the process tree with all the
        pipes used for IPC and calls the function (in <tt>trapezoidal.c</tt>) to
        evaluate integrals and prints out the result.
</p>
</ul>
<p>
    This provided <tt>Makefile</tt> takes care of linking in the <tt>cs551f10</tt> library
    at compile-time.
</p>
<p><dt><a href="./files/fns.h">./files/fns.h</a><dd>
    The header file which specifies how the functions to be integrated
    are made available to the program.
</p>
<p><dt><a href="./files/fns.c">./files/fns.c</a><dd>
    A sample file containing a couple of functions which can be integrated.
</p>
</dl>
<h2>Caution</h2>
<p>
<b>IMPORTANT</b>: In this project, you will be creating multiple processes.  It
is important that you ensure that you do not create runaway processes and
that you clean up any garbage processes periodically and definitely before
you logout.
</p>
<p>
<tt>bingsuns</tt> appears to have a hard limit of 128 on the number of processes
each user can create (the <tt>maxuprc</tt> parameter in <tt>/etc/system</tt>).  This is
more than adequate for this project and should protect you from overloading
the system.  In spite of this protection, be extra careful in the code where
you are forking processes.  You probably should not specify command-line
parameters which are expected to generate more than 10 - 20 processes.
</p>
<p>
You can see what processes you have running using the <tt>ps</tt> command with the
options <tt>-jf</tt>.  The PID and PGID columns are relevant as arguments to the
kill command (the kill command can be used to kill multiple processes by
specifying the PGID as a negative number).  For example:
</p>
<pre>
bingsun2% ps -jf
     UID   PID  PPID  PGID   SID  C    STIME TTY      TIME CMD
 umrigar 11368 11199 11368 11368  0 02:18:33 pts/14   0:00 /bin/bash -i
 umrigar 11636 11369 11636 11368  0 02:42:59 pts/14   0:00 ps -jf
 umrigar 11369 11368 11369 11368  0 02:18:36 pts/14   0:00 tcsh
bingsun2% /bin/perl -e 'fork(); fork(); sleep 50;' &amp;
[1] 11637
bingsun2% ps -jf
     UID   PID  PPID  PGID   SID  C    STIME TTY      TIME CMD
 umrigar 11639 11637 11637 11368  0 02:43:08 pts/14   0:00 /bin/perl -e fork(); fork(); sleep 50;
 umrigar 11640 11638 11637 11368  0 02:43:08 pts/14   0:00 /bin/perl -e fork(); fork(); sleep 50;
 umrigar 11641 11369 11641 11368  0 02:43:11 pts/14   0:00 ps -jf
 umrigar 11368 11199 11368 11368  0 02:18:33 pts/14   0:00 /bin/bash -i
 umrigar 11638 11637 11637 11368  0 02:43:08 pts/14   0:00 /bin/perl -e fork(); fork(); sleep 50;
 umrigar 11637 11369 11637 11368  0 02:43:08 pts/14   0:00 /bin/perl -e fork(); fork(); sleep 50;
 umrigar 11369 11368 11369 11368  0 02:18:36 pts/14   0:00 tcsh
bingsun2% /bin/kill -- -11637
bingsun2%
[1]    Terminated                    /bin/perl -e fork(); fork(); sleep 50;
bingsun2% ps -jf
     UID   PID  PPID  PGID   SID  C    STIME TTY      TIME CMD
 umrigar 11644 11369 11644 11368  0 02:43:30 pts/14   0:00 ps -jf
 umrigar 11368 11199 11368 11368  0 02:18:33 pts/14   0:00 /bin/bash -i
 umrigar 11369 11368 11369 11368  0 02:18:36 pts/14   0:00 tcsh
bingsun2%
</pre>
<p>
The first command lists the current processes.  This is followed be a <tt>perl</tt>
command to fork several processes in the background.  These are listed using
the third command.  The fourth command kills off the perl processes by
specifying their PGID and the final command lists the processes again to
ensure that the perl processes have indeed been killed.
</p>
<h2>Discussion</h2>
<p>
You will need to distinguish between two kinds of processes:
</p>
<dl>
<p><dt><b>Summation processes</b><dd>
     Processes internal to the process tree whose only function is
     to sum the results computed by their children.
</p>
<p><dt><b>Integration processes</b><dd>
     Leaf processes in the process tree whose function is to integrate
     the specified function over a subset of the specified range.
</p>
</dl>
<p>
Note that the number of steps is reduced for each process at greater
level numbers.  Hence, it is perfectly reasonable to expect that for some
inputs the number of steps for some processes will shrink down to zero.
</p>
<p>
For IPC, you will need two half-duplex pipes (with a total of 4 file
descriptors) between each parent and child process:
</p>
<ul>
<p><li>
One pipe will be used to send the integration parameters from
    the parent to the child.
</p>
<p><li>
One pipe will be used to send the results from the child to
    the parent.
</p>
</ul>
<p>
There are many possible choices you can make about the format of the data
you send on the pipes.  Two choices are:
</p>
<ul>
<p><li>
Binary data.  You send the integration parameters from a parent to a
    child as a binary structure and you receive the integration result from
    a child as a binary double.
</p>
<p><li>
Textual data.  You send the integration parameters from a parent to a
    child in a format identical to that specified for input to the program.
    You return the integration result from a child to a parent as a binary
    double.
</p>
</ul>
<p>
Binary protocols are useful when performance is important; textual protocols
are more flexible and portable and easier to debug.
</p>
<p>
Another choice you can make is whether to redirect standard input and
standard output to the pipe descriptors whenever possible.  Specifically:
</p>
<ul>
<p><li>
A summation process can read results its children using multiple pipe
    descriptors (as many descriptors as there are children) but write its
    result to standard output (redirected from a pipe descriptor if
    applicable).
</p>
<p><li>
A integration process (which is necessarily a leaf process) can read its
    input from standard input (redirected from a pipe descriptor) and write
    its result to standard output (redirected from a pipe descriptor).
</p>
</ul>
<p>
The advantage of redirecting standard input and output to pipe descriptors
is that if you have used the textual data representation outlined above then
you can setup the root process as just another summation process whose
standard output has not been redirected away from the program's standard
output (normally the terminal).  Another advantage is that it is easy to
test the integration processes with standard input and output rather than
arbitrary pipe descriptors.
</p>
<p>
Another choice to make is whether to use C's standard I/O.  Advantages
include the ability to use formatted I/O routines like <tt>printf()</tt>,
<tt>scanf()</tt>.  The disadvantages include the necessity of converting the pipe
file descriptors to <tt>FILE *</tt> streams (using <tt>fdopen()</tt>) and remembering to
flush buffers (using <tt>fflush()</tt>) as otherwise I/O across pipes would block.
</p>
<p>
When the program detects normal termination (using EOF), the root process
should close off the descriptors/streams writing to its children and then
wait for its children to terminate.  This closure should be propagated down
the tree with parents waiting for their children to terminate.  At the
lowest level, when the leaf processes detect EOF on their input, they should
terminate.  This should result in termination of waiting parents
successively up the levels of the tree, finally resulting in termination of
the root process and the entire program.
</p>
<p>
The fact that you are not allowed to have any fixed limits in the program
and that the parameters which shape the process tree are not known till
runtime will force you to use dynamic allocation for entities like:
</p>
<ul>
<p><li>
Descriptors or <tt>FILE *</tt> pointers used for reading/writing the child
    processes.
</p>
<p><li>
Memory used for specifying the problem parameters to each process.
</p>
<p><li>
Possibly for child PID's depending on which form of wait call you decide
    to use.
</p>
</ul>
<h2>Submission</h2>
<p>
You should submit a archive <tt>prj2.tar.gz</tt> which contains all the source
files needed to build your project.
</p>
<ul>
<p><li>
The archive should not contain any executable or object files.
</p>
<p><li>
The provided <a href="./files/Makefile">Makefile</a> contains a <tt>submit</tt>
    target such that typing <tt>make submit</tt> will build the required
    <tt>prj2.tar.gz</tt> archive.  This presupposes that you have edited the
    <tt>Makefile</tt> to adjust it if you have a different organization for your
    source files than that outlined above.
</p>
<p><li>
The archive <b>must</b> contain a <tt>Makefile</tt> such that typing <tt>make</tt> in the
    directory containing the unpacked archive should build your project's
    main executable <tt>prj2</tt>.  You can test this before submission, by
    unpacking your archive into an empty directory and checking to see
    whether typing <tt>make</tt> builds correctly.
</p>
<p><li>
Your submission <b>must</b> include a <tt>README</tt> file which minimally contains
    at least your name and ID number.  It can optionally contain any
    comments you feel are relevant to the project like what works, what does
    not work, what you feel is neat, logs of test cases, etc.
</p>
<p><li>
Your submission should include any files from the <a href="./files">./files</a> directory
    your project uses, whether you modified them or not.  You will not need
    to modify the <tt>Makefile</tt> if you use exactly the same names and
    organization as that in the provided <a href="./files/Makefile">Makefile</a>.
</p>
<p><li>
You do not need to include any files used from the <tt>cs551s10</tt> library.
</p>
</ul>
<p>
The above archive should be email'd as an attachment to the TA at
<a href="mailto:ruiqi.luo@gmail.com">mailto:ruiqi.luo@gmail.com</a> with subject set to <tt>CS 451/551 Project 2</tt>.  If
you discover a mistake in your submitted project before the due date, you
may submit it again; only the latest submission will be graded.
</p>
</body>
</html>
